package com.acwing.partition35;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/3/13 16:38
 */
public class AC3419双向排序_栈 {

    private static final int N = 100010;
    private static Node[] stk = new Node[N];
    private static int[] ans = new int[N];
    private static int n, m;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] ss = reader.readLine().split(" ");
        n = Integer.parseInt(ss[0]);
        m = Integer.parseInt(ss[1]);
        int top = 0;
        while (m-- > 0) {
            ss = reader.readLine().split(" ");
            int op = Integer.parseInt(ss[0]), k = Integer.parseInt(ss[1]);
            if (op == 0) {
                //找出连续操作的最长前缀
                while (top != 0 && stk[top].op == 0) k = Math.max(k, stk[top--].k);
                while (top >= 2 && stk[top - 1].k <= k) top -= 2;
                stk[++top] = new Node(0, k);
            } else if (top != 0) {
                //找出连续操作的最长后缀
                while (top != 0 && stk[top].op == 1) k = Math.min(k, stk[top--].k);
                while (top >= 2 && stk[top - 1].k >= k) top -= 2;
                stk[++top] = new Node(1, k);
            }
        }
        int k = n, l = 1, r = n;
        for (int i = 1; i <= top; i++) {
            if (stk[i].op == 0) {
                //若为前缀操作，则(stk[i].k, r]不用操作，直接填充数字
                while (r > stk[i].k && l <= r) ans[r--] = k--;
            } else {
                //若为后缀操作，则[l, stk[i].k)不用操作，直接填充数字
                while (l < stk[i].k && l <= r) ans[l++] = k--;
            }
            if (l > r) break;
        }
        //若l < r, 表示中间还有些数没有填上，操作次数为奇数，则下一次操作为前缀操作
        if (top % 2 == 1) {
            while (l <= r) ans[l++] = k--;
        } else {
            while (l <= r) ans[r--] = k--;
        }
        for (int i = 1; i <= n; i++) writer.write(ans[i] + " ");
        writer.flush();
    }

    private static class Node {
        private int op, k;

        public Node(int op, int k) {
            this.op = op;
            this.k = k;
        }
    }
}
